CLOS networks, which are 3-stage unidirectional switching networks, are well known in the art. As depicted in FIG. 1, a typical CLOS network 100 includes a source stage 102 that includes a plurality of R source modules 102-1 to 102-R, wherein each source switching module is a Nxc3x97M switch, which may be a crossbar switch. The M output ports of the R source modules are connected to the input ports of a midstage switching stage 104. The midstage switching stage 104 includes M midstage switching modules 104-1 to 104-M each having R input ports, wherein each of the midstage switching modules 104 is an Rxc3x97R switch, which may be a crossbar switch. The R output ports of the midstage switching modules are connected to the input ports of a destination stage 106. The destination stage 106 includes R destination modules, 106-1 to 106-R wherein each of the R destination modules is an Mxc3x97N switch, which may be a crossbar switch. Thus, for each of the R source modules 102 there is exactly one connection, i.e., one unit of edge capacity, between the source module and any midstage switching module. Similarly, there is exactly one connection, i.e., one unit of edge capacity, between each of the M midstage switching modules and each of the R destination modules.
As used herein an input circuit is an input signal having one or more component signals. An input circuit typically is applied or allocated to an input port on one of the source switching modules. A unicast input circuit is an input circuit that has a single source port and a single destination port. A dualcast input circuit is an input circuit that has a single source port and two destination ports on one or more destination switching modules, and a multicast input circuit is an input circuit that has a single source port and more than two destination ports on one or more switching modules.
A 3-stage CLOS network is strict sense non-blocking when carrying unicast circuits when there is no need to re-route any existing circuits to allow the switching of a new input circuit from the desired source module to the desired destination module. A sufficient condition for strict sense non-blocking of unicast input circuits is that the number of output ports per source switching module and therefore the number of midstage switching modules M is greater than or equal to 2 times the number of input ports per source module minus 1, or Mxe2x89xa72*Nxe2x88x921.
A 3-stage CLOS network is considered reconfigurably non-blocking when carrying unicast circuits when to accommodate a new input circuit, existing circuits may have to be re-routed within the CLOS network. A sufficient condition for unicast reconfigurably non-blocking is that the number of midstage switching modules is greater than or equal to the number of input ports on a source module, or Mxe2x89xa7N.
A 3-stage CLOS network is strict sense non-blocking when carrying dualcast circuits when there is no need to re-route any existing circuits to allow the switching of a new input circuit from the desired source module to the desired destination modules. A sufficient condition for dualcast strict sense non-blocking is that the number of output ports per source switching module, and therefore the number of midstage switching modules, M is greater than or equal to 3 times the number of input ports per source module minus 2, or Mxe2x89xa73*Nxe2x88x922.
A 3-stage CLOS network is considered reconfigurably non-blocking when carrying dualcast circuits when to accommodate a new input circuit an existing circuit may have to be re-routed within the CLOS network. A sufficient condition for dualcast reconfigurably non-blocking is that the number of midstage switching modules is greater than or equal to twice the number of input ports on a source module, or Mxe2x89xa72N. A necessary condition for dualcast reconfigurably nonblocking is that the number of midstage switching modules is greater than or equal to four-thirds times the number of input ports on a source module, or Mxe2x89xa74N/3.
Typically, CLOS networks may have several hundred input ports distributed among tens or hundreds of source modules. To provide a suitable quality of connectivity the CLOS network should be configured to be at least reconfigurably nonblocking. However, as the size of the CLOS network grows, reconfiguring the CLOS network involves coordinating switchovers in all three switching stages. This recoordination is time consuming and may lead to traffic disruptions resulting in loss of data. For example re-routing an existing circuit may result in traffic disruptions that are greater than 50 ms. Therefore, creating a system that is reconfigurably nonblocking is not an efficient network architecture and can be disruptive to the traffic carried thereon. As discussed above, to ensure strict sense non-blocking for large CLOS networks, the required number of midstage switching modules must increase at twice to three times the rate as the number of input ports. This can lead to large, expensive, and complex switching systems.
Therefore it would be desirable to provide a 3-stage CLOS network that is not as large and complex as a strict sense non-blocking network, does not require reconfiguration as a reconfigurable non-blocking network, but provides a suitably low blocking probability of a circuit.
A method and apparatus are disclosed for spreading an input circuit through a three-stage CLOS network such that the CLOS network has an extremely small blocking probability. In one embodiment, a method is provided that includes receiving an incoming input circuit that includes a plurality of component signals and also has associated therewith a source and destination identifier. Each component signal has further associated therewith a bandwidth requirement. The input circuit is allocated to one of a plurality of source switching modules that corresponds to the source identifier associated with the input circuit. At least two of the component signals are to be spread over the various midstage switching modules. As such, an ordered list is made that includes each of the midstage switching modules, and each midstage switching module is evaluated in order to identify a first midstage switching module that has a first connection to the source switching module corresponding to the source identifier, and a second connection to the destination switching module corresponding to the destination identifier. If both the first and second connections have sufficient spare bandwidth to accommodate the bandwidth of the first component signal, the first component signal is routed through the first midstage switching module. The search for a second midstage switching module to route the second component signal through begins with the next midstage switching module in the ordered list. Each midstage switching module is again evaluated to identify a second midstage switching module that has a first connection to the source switching module corresponding to the source identifier, and a second connection to the destination switching module corresponding to the destination identifier. If both the first and second connections have sufficient spare bandwidth to accommodate the bandwidth of the second component signal, the second component signal is routed through the second midstage switching module.
In one embodiment, if the search for a second midstage switching module has reached the last midstage switching module in the ordered list and not all of the midstage switching modules have been evaluated, the search for a second midstage switching module continues from the first midstage switching module of the ordered list and will continue up to and including the first midstage switching module.
An input circuit that is be a multicast circuit includes two or more identified destinations for a single identified source. A dualcast circuit is a multicast circuit having two identified destinations for a single identified source. These multicast circuits must be split at either the first or second switching module to arrive at the various identified destinations.
In one embodiment in which dualcast or multi-cast circuits are input to the CLOS network the splitting of the multicast or dualcast signals can be performed either at the source switching module or the midstage switching module or a combination of source stage spreading and midstage spreading may be employed. These may be employed with the other spreading and load balancing techniques discussed in more detail below.